Este teorema demuestra que es posible codificar un árbol con una secuencia de N-2 números -donde N es el número de nodos-.
Se detalla un ejemplo que muestra el algoritmo de obtención de la secuencia de números, y la recuperación del árbol a partir de la secuencia
Teorema de enumeración
El teorema de enumeración de Cayley que define que existen nn-2 distintos árboles etiquetados en un grafo G con n vértices, puede ser demostrado con el teorema de enumeración de Prüfer, el cual establece una correspondencia uno a uno entre tales árboles y el conjunto de todas las cadenas de n-2 enteros donde cada entero esta entre n y 1 inclusive.
Prüfer observó que para cualquier árbol existen por lo menos dos vertices de grado uno. Así en un árbol etiquetado T, el vértice v incidente al vértice etiquetado con etiqueta más baja de grado uno es determinado en forma única, y v se convierte en el primer simbolo de la cadena. Una vez que se ha borrado este arco tenemos un árbol con n-1 vértices. Repitiendo esta operación hasta que solo quede un arco produce n-2 enteros entre 1 y n inclusive.
Para reconstruir un árbol T desde una codificación de Prüfer observamos que cualquier vértice aparecera en la codificación exactamente una vez menos que el grado del vértice en T. Los nodos hoja, que tienen grado uno, no aparecerán en el código. Así es posible contar el grado de todos los vértices de T, e identificar el vértice etiquetado de grado uno más bajo en el árbol.
Este teorema puede ser utilizado para formalizar el espacio de búsqueda como n-2 pasos.
En la recuperación del grafo se utiliza la cadena obtenida y una cadena auxiliar en donde se enumeran los nodos que no aparecen en la primera.
1.Unir el primer elemento de la cadena obtenida -enumeración- con el elemento menor de la cadena auxiliar, los cuales representan la etiqueta de los nodos respectivos.
2. Eliminar ambos elementos de las cadenas.
3. Si no existen más ocurrencias del elemento borrado en la enumeración, entonces anexar el elemento a la cadena auxiliar.
4. Si en la cadena auxiliar existen solo dos elementos, entones unirlos en el grafo y terminar, en caso contrario, regresar al paso 1.
Aplicar el Teorema de Prüfer para obtener la enuneración del grafo presentado en la figura , una vez obtenida dicha enumeración, demostrar que ésta es quivalente al grafo original.
Recuperación